package _dp_base;

/**
 * 63. 不同路径 II
 */
public class No63 {
    private int[][] obstacleGrid;
    private int[][] cache;

    /**
     * 1. 递归
     */
    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        cache = new int[m][n];
        cache[0][0] = 1;
        return dfs(m - 1, n - 1);
    }

    private int dfs(int i, int j) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) return 0;
        else if (cache[i][j] != 0) return cache[i][j];
        else return cache[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    }

    /**
     * 2. 迭代
     */
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] f = new int[m + 1][n + 1];
        f[1][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) f[i + 1][j + 1] = 0;
                else if (i != 0 || j != 0) f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j];
            }
        }

        return f[m][n];
    }

    /**
     * 4. 一维数组
     */
    public int uniquePathsWithObstacles4(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;

        int[] f = new int[n + 1];
        f[1] = 1;
        for (int[] ints : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (ints[j] == 1) f[j + 1] = 0;
                else f[j + 1] = f[j + 1] + f[j];
            }
        }

        return f[n];
    }
}
